/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
    let s1 = text1.length;
    let s2 = text2.length;
    let memo = new Map();

    let dp = function (i, j) {
        // 空串的base case
        if (i === -1 || j === -1) {
            return 0;
        }

        // 查询一下备忘录，防止重复计算
        let key = i + "," + j
        if (memo.has(key)) {
            return memo.get(key)
        }

        let res;
        if (text1[i] === text2[j]) {
            // 这边找到一个 lcs 的元素，继续往前找
            // 记入备忘录
            res = dp(i - 1, j - 1) + 1
            memo.set(key, res)
        } else {
            // 谁能让lcs最长，就听谁的
            res = Math.max(dp(i - 1, j), dp(i, j - 1))
            memo.set(key, res)
        }
        return res;
    }
    // i 和 j 初始化为最后一个索引
    return dp(s1 - 1, s2 - 1)
};

var longestCommonSubsequence = function (text1, text2) {
    let s1 = text1.length;
    let s2 = text2.length;

    // 构建 DP table 和 base case
    // 初始化一个 （s1+1）*（s2+1）的dp表
    let dp = new Array(s1 + 1);
    for (let i = 0; i < s1 + 1; i++) {
        dp[i] = new Array(s2 + 1);
        dp[i].fill(0, 0, s2 + 1)
    }

    // 进行状态转移
    for (let i = 1; i < s1 + 1; i++) {
        for (let j = 1; j < s2 + 1; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                // 找到一个lcs中的字符
                dp[i][j] = 1 + dp[i - 1][j - 1]
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }

    // i 和 j 初始化为最后一个索引
    return dp[s1][s2]
};


